#ifndef DEPTHFIRSTSEARCH_H
#define DEPTHFIRSTSEARCH_H

#include <QtCore>

#include <igraph.h>

namespace sk {

class DepthFirstSearch {
public:
    DepthFirstSearch(CGraph* graph, int vertex) : graph(graph), v(vertex), allocSz(graph->getVerticesCount() + 1), debug(true) {
        colors = new int[allocSz];
        clock1 = new int[allocSz];
        clock2 = new int[allocSz];
    }

    ~DepthFirstSearch() {
        delete[] colors;
        delete[] clock1;
        delete[] clock2;
    }

    virtual void preProcessVertex(int vertex) {
        if(debug) printf("preProcess: %d\n", vertex);
    }

    virtual void postProcessVertex(int vertex) {
        if(debug) printf("postProcess: %d\n", vertex);
    }

    virtual void processEdge(int from, int to) {
        if(debug) printf("edge: %d -> %d\n", from, to);
    }

    virtual void process(int vertex) {
        if(debug) printf("Process: %d\n", vertex);
    }

    enum Color {
        COLOR_WHITE, COLOR_GREY, COLOR_BLACK
    };

    void go() {
        clock = 0;
        memset(clock1, 0, sizeof(clock1) * allocSz);
        memset(clock2, 0, sizeof(clock1) * allocSz);
        memset(colors, COLOR_WHITE, sizeof(clock1) * allocSz);

        visit(v);
    }

    void visit(int vertex) {
        if (colors[vertex] != COLOR_WHITE) return;

        preProcessVertex(vertex);

        clock1[vertex] = ++clock;

        process(vertex);

        colors[vertex] = COLOR_GREY;
        const QList<int>& children = graph->getAdjanancies(vertex);
        foreach(int v, children) {
            processEdge(vertex, v);
            visit(v);
        }
        postProcessVertex(vertex);

        colors[vertex] = COLOR_BLACK;
        clock2[vertex] = ++clock;
    }

    void debug_toString() {
        printf("allocSz: %d\n", allocSz);

        for (int i = 0; i < allocSz; i++) printf("  colors[%d] = %d\n", i, colors[i]);
        for (int i = 0; i < allocSz; i++) printf("  clock1[%d] = %d\n", i, clock1[i]);
        for (int i = 0; i < allocSz; i++) printf("  clock2[%d] = %d\n", i, clock2[i]);
    }

protected:
    bool debug;

private:
    CGraph* graph;
    int v;
    int allocSz;

    int* colors;
    int* clock1;
    int* clock2;
    int clock;
};

}

#endif // DEPTHFIRSTSEARCH_H
